{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Convert Sorted Array to Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-search-tree #array #divide-and-conquer #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉搜索树 #数组 #分治 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortedArrayToBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将有序数组转换为二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，其中元素已经按 <strong>升序</strong> 排列，请你将其转换为一棵 <strong>高度平衡</strong> 二叉搜索树。</p>\n",
    "\n",
    "<p><strong>高度平衡 </strong>二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/18/btree1.jpg\" style=\"width: 302px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-10,-3,0,5,9]\n",
    "<strong>输出：</strong>[0,-3,9,-10,null,5]\n",
    "<strong>解释：</strong>[0,-10,5,null,-3,null,9] 也将被视为正确答案：\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/18/btree2.jpg\" style=\"width: 302px; height: 222px;\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/18/btree.jpg\" style=\"width: 342px; height: 142px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,3]\n",
    "<strong>输出：</strong>[3,1]\n",
    "<strong>解释：</strong>[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>nums</code> 按 <strong>严格递增</strong> 顺序排列</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [convert-sorted-array-to-binary-search-tree](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [convert-sorted-array-to-binary-search-tree](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-10,-3,0,5,9]', '[1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if nums == []: return(None)\n",
    "        iMiddle = int(len(nums)/2)\n",
    "        head = TreeNode(val = nums[iMiddle])\n",
    "        head.left = self.sortedArrayToBST(nums[0:iMiddle])\n",
    "        head.right = self.sortedArrayToBST(nums[iMiddle+1:])\n",
    "        return(head)\n",
    "\n",
    "        \n",
    "# Test Cases: \n",
    "#\n",
    "#\n",
    "# [] --> Not Valid \n",
    "# [3] --> [3]\n",
    "# \n",
    "# [1 2] -->  1       -->     2\n",
    "#               2          1\n",
    "# \n",
    "# [1 2 3 4 5 6 7 8]       4\n",
    "# -->                   2     6\n",
    "#                      1 3  5   8\n",
    "#                              7\n",
    "#\n",
    "#\n",
    "#\n",
    "#                       time        space\n",
    "# Approach 1:           O(n)        O(n)\n",
    "# Split list in \"half\", hand left and right sides recursively\n",
    "#\n",
    "# Aproach 2: Consider later \n",
    "# \"Bottom Up\"\n",
    "#\n",
    "# "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.makeTree(0, len(nums)-1, nums)\n",
    "    \n",
    "    def makeTree(self, left, right, a):\n",
    "        if left > right:\n",
    "            return None\n",
    "        mid = (left + right) // 2\n",
    "        root = TreeNode(a[mid])\n",
    "        root.left = self.makeTree(left, mid-1, a)\n",
    "        root.right = self.makeTree(mid+1, right, a)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: 'List[int]') -> 'TreeNode':\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return None\n",
    "        c = n // 2\n",
    "        root = TreeNode(nums[c])\n",
    "        root.left = self.sortedArrayToBST(nums[:c])\n",
    "        root.right = self.sortedArrayToBST(nums[c+1:])\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, root, nums, s, e):\n",
    "        if s > e:\n",
    "            return None\n",
    "        mid = s + (e - s) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.buildTree(root.left, nums, s, mid-1)\n",
    "        root.right = self.buildTree(root.right, nums, mid+1, e)\n",
    "        return root\n",
    "    \n",
    "    def sortedArrayToBST(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        tot = len(nums)\n",
    "        e = tot - 1\n",
    "        root = None\n",
    "        root = self.buildTree(root, nums, 0, e)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=108 lang=python3\n",
    "#\n",
    "# [108] 将有序数组转换为二叉搜索树\n",
    "#\n",
    "# https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (59.72%)\n",
    "# Total Accepted:    11.8K\n",
    "# Total Submissions: 19.8K\n",
    "# Testcase Example:  '[-10,-3,0,5,9]'\n",
    "#\n",
    "# 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。\n",
    "#\n",
    "# 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。\n",
    "#\n",
    "# 示例:\n",
    "#\n",
    "# 给定有序数组: [-10,-3,0,5,9],\n",
    "#\n",
    "# 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：\n",
    "#\n",
    "# ⁠     0\n",
    "# ⁠    / \\\n",
    "# ⁠  -3   9\n",
    "# ⁠  /   /\n",
    "# ⁠-10  5\n",
    "#\n",
    "#\n",
    "#\n",
    "# Definition for a binary tree node.\n",
    "\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        root = self.binarySearch(nums, 0, len(nums) - 1)\n",
    "        return root\n",
    "\n",
    "    def binarySearch(self, nums, low, high):\n",
    "        if low > high:\n",
    "            return None\n",
    "        mid = (low + high) // 2\n",
    "        print(\"log\")\n",
    "        print(mid)\n",
    "        node = TreeNode(nums[mid])\n",
    "        node.left = self.binarySearch(nums, low, mid - 1)\n",
    "        node.right = self.binarySearch(nums, mid + 1, high)\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return None\n",
    "        mid = len(nums)//2\n",
    "        root = TreeNode(nums[mid])\n",
    "        left = nums[:mid]\n",
    "        right = nums[mid+1:]\n",
    "        root.left = self.sortedArrayToBST(left)\n",
    "        root.right = self.sortedArrayToBST(right)\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        size = len(nums)\n",
    "        if size == 0:\n",
    "            return None\n",
    "        elif size == 1:\n",
    "            return TreeNode(nums[0])\n",
    "        size //= 2\n",
    "        print(size)\n",
    "        root = TreeNode(nums[size])\n",
    "        root.left = self.sortedArrayToBST(nums[:size])\n",
    "        root.right = self.sortedArrayToBST(nums[size+1:])\n",
    "        return root\n",
    "       \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.bulidTree(nums)\n",
    "    def bulidTree(self,nums):\n",
    "            if not nums:\n",
    "                return None\n",
    "            mid=int(len(nums)/2)\n",
    "            print(mid)\n",
    "            root=TreeNode(nums[mid])\n",
    "            root.left=self.bulidTree(nums[:mid])\n",
    "            root.right=self.bulidTree(nums[mid+1:])\n",
    "            return root\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        node=Node(nums)\n",
    "        return node.get()\n",
    "        \n",
    "        \n",
    "class Node:\n",
    "    def __init__(self,figs):\n",
    "        if len(figs)==0:\n",
    "            self.fig=None\n",
    "            self.left=None\n",
    "            self.right=None\n",
    "        else:\n",
    "            index=len(figs)//2\n",
    "            self.fig=figs[index]\n",
    "            self.left=Node(figs[:index])\n",
    "            self.right=Node(figs[index+1:])\n",
    "    def get(self):\n",
    "        if self.fig is None:\n",
    "            return None\n",
    "        r=TreeNode(self.fig)\n",
    "        r.left=self.left.get()\n",
    "        r.right=self.right.get()\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "\n",
    "        rt = []\n",
    "        q = []\n",
    "        \n",
    "        q.append(nums)\n",
    "        \n",
    "        while q:\n",
    "            array = q.pop(0)\n",
    "            if array:   \n",
    "                mid = len(array)//2\n",
    "                rt.append(array[mid])\n",
    "                q.append(array[0:mid])\n",
    "                q.append(array[mid+1:])\n",
    "            else:\n",
    "                rt.append(None)\n",
    "        index = len(rt) - 1\n",
    "        while index > -1:\n",
    "            if rt[index] == None:\n",
    "                index -= 1\n",
    "            else:\n",
    "                return rt[0:index+1]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if len(nums)==0:\n",
    "            return None\n",
    "        begin=0\n",
    "        mid=int(len(nums)/2)\n",
    "        end=len(nums)-1\n",
    "        t=TreeNode(nums[mid])\n",
    "        t.left=self.sortedArrayToBST(nums[begin:mid])\n",
    "        t.right=self.sortedArrayToBST(nums[mid+1:end+1])\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return None\n",
    "        mid = len(nums)//2\n",
    "        Node = TreeNode(nums[mid])\n",
    "        left = nums[:mid]\n",
    "        right = nums[mid+1:]\n",
    "        Node.left = self.sortedArrayToBST(left)\n",
    "        Node.right = self.sortedArrayToBST(right)\n",
    "        return Node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if len(nums)==0:\n",
    "            return None\n",
    "        node = TreeNode(nums[len(nums) // 2])\n",
    "        \n",
    "        if len(nums) == 1:\n",
    "            return node\n",
    "        \n",
    "        if len(nums)>1:\n",
    "            node.left = self.sortedArrayToBST(nums[0:len(nums)//2])\n",
    "            node.right = self.sortedArrayToBST(nums[len(nums)//2+1:len(nums)])\n",
    "        return node\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def construct(left,right):\n",
    "            if left>right:\n",
    "                return None\n",
    "            p = (left+right)//2\n",
    "            root = TreeNode(nums[p])\n",
    "            root.left = construct(left,p-1)\n",
    "            root.right = construct(p+1,right)\n",
    "            return root\n",
    "        return construct(0,len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def createtree(left,right) -> TreeNode:\n",
    "            if left >=right:return None\n",
    "            mid = (left+right)//2 \n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = createtree(left,mid)\n",
    "            root.right = createtree(mid+1,right)\n",
    "            return root\n",
    "        return createtree(0,len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return None\n",
    "        n = len(nums)\n",
    "        x = n // 2\n",
    "        node = TreeNode(nums[x])\n",
    "        node.left = self.sortedArrayToBST(nums[0:x])\n",
    "        node.right = self.sortedArrayToBST(nums[x+1:n])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        nums_len = len(nums)\n",
    "        if nums_len == 0:\n",
    "            return None\n",
    "        mid = int(nums_len / 2)\n",
    "        tree = TreeNode(val=nums[mid],\n",
    "                        left=self.bstHelper(nums, 0, mid),\n",
    "                        right=self.bstHelper(nums, mid + 1, nums_len)\n",
    "                        )\n",
    "        return tree\n",
    "\n",
    "    def bstHelper(self, nums, start, end):\n",
    "        if start >= end:\n",
    "            return\n",
    "\n",
    "        mid = int((end + start) / 2)\n",
    "        node = TreeNode(val=nums[mid],\n",
    "                        left=self.bstHelper(nums, start, mid),\n",
    "                        right=self.bstHelper(nums, mid + 1, end))\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        node = TreeNode()\n",
    "        if nums:\n",
    "            mid = len(nums) // 2\n",
    "            node.val = nums[mid]\n",
    "            node.left = self.sortedArrayToBST(nums[:mid]) if nums[:mid] else None\n",
    "            node.right = self.sortedArrayToBST(nums[mid+1:]) if nums[mid+1:] else None\n",
    "        else:\n",
    "            node.val = None\n",
    "        return node\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        mid = len(nums) // 2\n",
    "\n",
    "        root = TreeNode(nums[mid])\n",
    "\n",
    "        root.left = self.sortedArrayToBST(nums[:mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid + 1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        n = len(nums)\n",
    "        if n == 0: return None\n",
    "        return TreeNode(nums[n // 2], self.sortedArrayToBST(nums[0: (n // 2)]), self.sortedArrayToBST(nums[(n // 2) + 1:]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        def build(left:int, right:int, nums: List[int])-> Optional[TreeNode]:\n",
    "            print(f\"left:{left}, right:{right}\")\n",
    "            if left > right:\n",
    "                return \n",
    "            mid = (left+right)//2\n",
    "            # print(f\"mid: {mid}\")\n",
    "            return TreeNode(nums[mid], build(left, mid-1,nums), build(mid+1, right,nums))\n",
    "           \n",
    "        return build(0, len(nums)-1, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        \n",
    "        def traversal(left, right):\n",
    "            if left > right:\n",
    "                return None\n",
    "            \n",
    "            mid = left + (right - left) // 2\n",
    "            node = TreeNode(val = nums[mid])\n",
    "            node.left = traversal(left, mid - 1)\n",
    "            node.right = traversal(mid + 1, right)\n",
    "\n",
    "            return node\n",
    "        \n",
    "        root = traversal(0, len(nums) - 1)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        mid = (left + right) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        q = deque([(root, left, mid, right)])\n",
    "        while q:\n",
    "            cur, left, mid, right = q.popleft()\n",
    "\n",
    "            left_mid = (left + mid) // 2\n",
    "            if left_mid < mid:\n",
    "                cur.left = TreeNode(nums[left_mid])\n",
    "                q.append((cur.left, left, left_mid, mid - 1))\n",
    "            \n",
    "            right_mid = (mid + right + 1) // 2\n",
    "            if right_mid > mid:\n",
    "                cur.right = TreeNode(nums[right_mid])\n",
    "                q.append((cur.right, mid+1, right_mid, right))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "        mid = len(nums)//2\n",
    "        root_val = nums[mid]\n",
    "        root = TreeNode(root_val)\n",
    "        root.left = self.sortedArrayToBST(nums[:mid]) #wrong [: mid-1]\n",
    "        root.right = self.sortedArrayToBST(nums[mid+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        \"\"\"\n",
    "        每次取中点作为root\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return None\n",
    "        n = len(nums)\n",
    "        mid = n//2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums[:mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        def make_tree(start_index, end_index):\n",
    "            if start_index > end_index:\n",
    "                return None\n",
    "            mid = (start_index + end_index) // 2\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = make_tree(start_index, mid - 1)\n",
    "            root.right = make_tree(mid + 1, end_index)\n",
    "            return root\n",
    "        return make_tree(0, len(nums) - 1)\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
